Kelahiran sempadan Indonesia-Malaysia, atau sekurang-kurangnya bahagian untuk apa yang sekarang Semenanjung Malaysia, boleh dikaitkan dengan perjanjian 1824 antara Great Britain dan Belanda yang ditandatangani di London pada tarikh 17 Mac 1824. Perjanjian tersebut menentukan lingkungan pengaruh di kepulauan Melayu antara dua kuasa penjajah - Great Britain dan Belanda. Great Britain dibenarkan menubuhkan tanah jajahan di utara Selat Melaka dan Selat Singapura manakala Belanda dibenarkan menjajah kawasan di selatan badan air. Garis pemisahan antara sfera pengaruh ini menjadi asas sempadan antara British Malaya dan Hindia Timur Belanda dan akhirnya, pengganti mereka menyatakan Malaysia dan Indonesia.

Di Borneo, perluasan kepentingan dan pengaruh British dan Belanda ke atas kesultanan dan kerajaan tempatan berlaku secara beransur-ansur sepanjang abad ke-19. Pantai utara Borneo menyaksikan pengembara British James Brooke menjadi Rajah Sarawak pada tahun 1842 dan secara beransur-ansur mengembangkan kerajaannya kepada bentuk dan saiz sekarang pada tahun 1905. Wilayah Sultan Brunei di Sabah hari ini pada mulanya diserahkan kepada kepentingan Austria, yang akhirnya jatuh ke tangan British, yang kemudiannya membentuk Syarikat Borneo Utara British . Sultan Sulu juga menyerahkan wilayahnya di pantai timur Sabah hari ini kepada British pada tahun 1878. Di bahagian selatan Borneo, Belanda sedang merundingkan perjanjian dengan pelbagai kesultanan, membenarkannya menjadi kuasa kolonial yang dominan di bahagian pulau itu. Pada tahun 1889, apabila wilayah yang diperoleh dari kedua-dua kuasa itu mula semakin hampir, satu suruhanjaya telah diwujudkan untuk mengesyorkan sempadan. Syor-syor tersebut telah disahkan dalam Konvensyen Sempadan 1891 yang ditandatangani di London pada Tarikh 20 Jun 1891. Sempadan itu dikemas kini dalam Perjanjian Sempadan 1915 yang ditandatangani di London pada Tarikh 28 September 1915, dan sekali lagi dalam Konvensyen Sempadan yang lain yang ditandatangani di The Hague, Belanda, pada Tarikh 26 Mac 1928. [22] [23]